GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Diamond-square Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Diamond-square Algorithmus</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Der Diamond-square Algorithmus ist ein Verfahren, das in der <a href="Computergrafik" title="Computergrafik">Computergrafik</a> eingesetzt wird, um <a href="H%C3%B6henfeld" title="Höhenfeld">Höhenfelder</a> zu erzeugen. Er stellt eine <a href="Zweidimensional" class="mw-redirect" title="Zweidimensional">2-dimensionale</a> Verallgemeinerung der Mittelpunktverschiebung dar. Der Algorithmus wurde erstmals 1982 von <a href="Alain_Fournier_(Informatiker)" title="Alain Fournier (Informatiker)">Fournier</a>, Fussell und Carpenter auf der <a href="SIGGRAPH" title="SIGGRAPH">SIGGRAPH</a> 1982 vorgestellt<a href="#cite_note-fournier1982computer-1">[1]</a>. Der Name geht zurück auf Gavin S. P. Miller<a href="#cite_note-miller1986definition-2">[2]</a>.

<div class="mw-heading mw-heading2"><h2 id="Funktionsweise">Funktionsweise</h2></div>

Ausgangspunkt für die Generierung einer fraktalen Landschaft auf Basis des Diamond-square Algorithmus ist ein Quadrat. Jeder Ecke des Quadrats wird ein Höhenwert zugeordnet. Der Algorithmus zerlegt das Quadrat <a href="Rekursiv" class="mw-redirect" title="Rekursiv">rekursiv</a> in kleinere Quadrate, wobei der Höhenwert des Mittelpunkts als Mittelwert der vier Eckpunkte, plus einer zufälligen Verschiebung, definiert wird. Analog wird der Höhenwert der <a href="Seitenhalbierende" title="Seitenhalbierende">Seitenhalbierenden</a> eines Quadrats als Mittelwert der vier horizontal umgebenden Punkte, plus einer zufälligen Verschiebung, definiert. Die Verschiebung ist <a href="Normalverteilung" title="Normalverteilung">Normalverteilt</a> mit einem <a href="Mittelwert" title="Mittelwert">Mittelwert</a> von 0 und nimmt mit der Größe der Rechtecke ab. Die Mittelpunkte und Seitenhalbierende bilden die Eckpunkte der neuen Rechtecke. Ausnahme von der Regel zur Generierung der neuen Punkte bilden die vier Außenseiten des ursprünglichen Rechtecks, die jeweils nach der eindimensionalen Mittelpunktverschiebung generiert werden<a href="#cite_note-fournier1982computer-1">[1]</a>.

Für den Diamond-square Algorithmus kommt ein 3x3-Raster, ein 5x5-Raster, ein 9x9-Raster, ein 17x17-Raster oder allgemein ein <a href="Quadratisch" class="mw-redirect" title="Quadratisch">quadratisches</a> Raster infrage, wo die Breite und Höhe gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}+1}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{n}+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e8e2d6ae605ac99baf648b70d204a3c9803a4d9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.384ex; height:2.509ex;" alt="{\displaystyle 2^{n}+1}" loading="lazy"> mit einer positiven <a href="Ganze_Zahl" title="Ganze Zahl">ganzen Zahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist. Jede <a href="Iteration" title="Iteration">Iteration</a> unterteilt jedes Quadrat in 4 gleich große Quadrate mit halber Seitenlänge und besteht aus 2 Schritten:

<ul><li>Karoschritt: Für jedes Quadrat des Rasters wird ein zufälliger Wert im Mittelpunkt erzeugt, wo sich die beiden Diagonalen des Quadrats schneiden. Der Wert für den Mittelpunkt wird berechnet, indem der Durchschnitt der Werte der 4 Ecken des Quadrats gebildet und ein zufälliger Betrag addiert wird. Dadurch entstehen Quadrate, die auf der Ecke stehen (Karos).</li>

<li>Quadratschritt: Für jedes quadratische Karo wird ein zufälliger Wert im Mittelpunkt erzeugt, wo sich die beiden Diagonalen des Karos schneiden. Der Wert für den Mittelpunkt wird berechnet, indem der Durchschnitt der Werte der 4 Ecken des Karos gebildet und ein zufälliger Betrag addiert wird, der im gleichen Bereich liegt wie im Karoschritt. Dadurch entstehen wieder Quadrate, die parallel zum Raster sind.</li></ul>

Jede <a href="Iteration" title="Iteration">Iteration</a> unterteilt jedes Quadrat also in 4 gleich große Quadrate mit halber Seitenlänge. Wenn die Prozedur 2-mal ausgeführt wird, entstehen aus jedem Quadrat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4^{2}=16}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4^{2}=16}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/891f0a31ba5eed6c31d8879cd3aa3aa66ecd2ea4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.64ex; height:2.676ex;" alt="{\displaystyle 4^{2}=16}" loading="lazy"> kleinere Quadrate mit gleicher Seitenlänge. Wenn die Prozedur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy">-mal ausgeführt wird, entstehen aus jedem Quadrat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 4^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 4^{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/563b380d4a8d0bb311093679b5696422a1c6f66d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 4^{k}}" loading="lazy"> kleinere Quadrate mit gleicher Seitenlänge.<a href="#cite_note-3">[3]</a>

Folgende Abbildung zeigt die ersten zwei Iterationen des Algorithmus für ein 5x5-Raster:

Dabei werden vier Schritte in der Reihenfolge Karoschritt, Quadratschritt, Karoschritt, Quadratschritt ausgeführt. Schon vorhandene Punkte sind schwarz, neu erzeugte Punkte sind gelb dargestellt.

<div class="mw-heading mw-heading2"><h2 id="Programmierung">Programmierung</h2></div>

Das folgende Beispiel in der <a href="Programmiersprache" title="Programmiersprache">Programmiersprache</a> <a href="C-Sharp" title="C-Sharp">C#</a> zeigt die Implementierung des Diamond-square Algorithmus. Das Höhenfeld wird als <a href="Zweidimensional" class="mw-redirect" title="Zweidimensional">zweidimensionales</a> Hintergrundbild des Hauptfensters dargestellt. Die berechneten Werte entsprechen den Farbwerten der <a href="Pixel" title="Pixel">Pixel</a> einer Bitmap.<a href="#cite_note-4">[4]</a>

<td style="text-align:left; font-size: 95%;">Code-Schnipsel

</td></tr>

<tr>

<td>

<div class="mw-highlight mw-highlight-lang-c# mw-content-ltr" dir="ltr"><pre>using System;

using System.Drawing;

using System.Windows.Forms;

namespace DiamondSquare

{

public class DiamondSquare

{

// Diese Methode berechnet die Werte mit dem Diamond-square Algorithmus

// Gegen ist die Seitenlänge des Quadrats, der Bereich für die zufälligen Werte und der Wert für die 4 Ecken des Quadrats

public double[,] CalculateValues(int length, double roughness, double seed)

{

// Initialisiert den Wert der 4 Ecken des Quadrats

double[,] values = new double[length, length]; // Initialisiert das zweidimensionale Array für die Werte des quadratischen Rasters

values[0, 0] = seed; // Wert der Ecke links oben

values[0, length - 1] = seed; // Wert der Ecke links unten

values[length - 1, 0] = seed; // Wert der Ecke rechts oben

values[length - 1, length - 1] = seed; // Wert der Ecke rechts unten

Random random = new Random(); // Initialisiert den Zufallsgenerator

// Diese for-Schleife definiert die Iterationsschritte des Algorithmus

// In jedem Iterationsschritt wird die Seitenlänge der Teilquadrate und der Bereich für die zufälligen Werte halbiert, bis die Seitenlänge kleiner als 2 ist

for (int sideLength = length - 1; sideLength >= 2; sideLength /= 2, roughness /= 2.0)

{

int halfLength = sideLength / 2;

// In diesen zwei for-Schleifen werden die Werte für den Karoschritt berechnet

for (int x = 0; x < length - 1; x += sideLength)

{

for (int y = 0; y < length - 1; y += sideLength)

{

// Berechnet den Mittelwert der 4 Ecken des Teilquadrats

double average = (values[x, y] // Wert der Ecke links oben

+ values[x, y + sideLength] // Wert der Ecke links unten

+ values[x + sideLength, y] // Wert der Ecke rechts oben

+ values[x + sideLength, y + sideLength]) / 4.0; // Wert der Ecke rechts unten

average += (2 * roughness * random.NextDouble()) - roughness; // Addiert einen zufälligen Wert im Bereich von -roughness bis +roughness zum Mittelwert

values[x + halfLength, y + halfLength] = average; // Setzt den Wert für den Mittelpunkt des Teilquadrats

}

// In diesen zwei for-Schleifen werden die Werte für den Quadratschritt berechnet

for (int x = 0; x < length - 1; x += halfLength)

{

for (int y = (x + halfLength) % sideLength; y < length - 1; y += sideLength)

{

// Berechnet den Mittelwert der 4 Ecken des Karos

double average = (values[(x - halfLength + length) % length, y] // Wert der linken Ecke

+ values[(x + halfLength) % length, y] // Wert der rechten Ecke

+ values[x, (y - halfLength + length) % length] // Wert der oberen Ecke

+ values[x, (y + halfLength) % length]) / 4.0; // Wert der unteren Ecke

average += (2 * roughness * random.NextDouble()) - roughness; // Addiert einen zufälligen Wert im Bereich von -roughness bis +roughness zum Mittelwert

values[x, y] = average; // Setzt den Wert für den Mittelpunkt des Karos

if (x == 0) // Sonderfall für die linke Kante des Quadrats

{

values[length - 1, y] = average; // Setzt den entsprechenden Punkt auf der rechten Kante auf denselben Wert

}

if (y == 0) // Sonderfall für die obere Kante des Quadrats

{

values[x, length - 1] = average; // Setzt den entsprechenden Punkt auf der unteren Kante auf denselben Wert

}

return values;

}

// Klasse für das Hauptfenster

public partial class MainForm : Form

{

private Bitmap bitmap;

private int length;

private double[,] values; // Zweidimensionales Array für die Werte des quadratischen Rasters

public MainForm()

{

Random random = new Random(); // Initialisiert den Zufallsgenerator

length = 257; // Seitenlänge des Quadrats, es ist 2^8 + 1 = 257

int roughness = 64; // Bereich für die zufälligen Werte

int seed = 128; // Wert für die 4 Ecken des Quadrats

DiamondSquare diamondSquare = new DiamondSquare(); // Erzeugt ein Objekt der Klasse DiamondSquare

values = diamondSquare.CalculateValues(length, roughness, seed); // Aufruf der Methode, die die Werte für das quadratische Raster berechnet und zurückgibt

bitmap = new Bitmap(length, length); // Erzeugt ein quadratisches Bitmap mit der gegebenen Seitenlänge

BackgroundImage = bitmap; // Setzt die Bitmap als Hintergrundbild des Hauptfensters.

InitializeComponent();

Text = "Diamond-square Algorithmus";

Width = 800;

Height = 800;

Paint += OnPaint; // Verknüpft die Ereignisbehandlungsmethode mit dem Paint Ereignis des Hauptfensters.

}

// Diese Methode wird aufgerufen, wenn das Hauptfenster gezeichnet wird und setzt die Pixel des Bitmaps

private void OnPaint(object sender, PaintEventArgs e)

{

// Diese for-Schleifen durchlaufen die Pixel des Bitmaps

for (int x = 0; x < length; x++)

{

for (int y = 0; y < length; y++)

{

bitmap.SetPixel(x, y, Color.FromArgb(0, (int) values[x, y], 0)); // Setzt den Farbwert des Pixels

}

}

</pre></div>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Mögliche_Implementierung_in_unterschiedlichen_Dimensionen">Mögliche Implementierung in unterschiedlichen Dimensionen</h2></div>

Es ist möglich, den Algorithmus in verschiedene Dimensionen zu übertragen und somit unterschiedliche Resultate zu erzielen. Hierbei wird eine n-dimensionale Einheit mit Tiefe versehen. Das heißt, dass für jede berechnete n-dimensionale Koordinate ein Wert, meist von 0 bis 1, vorhanden ist. Die optische Darstellung kann man entweder mit einer Verschiebung in der nächsten Dimensionsachse oder eine Farbe bzw. Transparenz realisieren. Hierbei ist die zweidimensionale Implementierung namensgebend.

<dl><dt>Beispiele</dt>

Bei einer dreidimensionalen Implementierung kann man sich zum Beispiel eine Karte für die Dichte von Nebel vorstellen. Hierbei werden unterschiedliche Areale unterschiedlich viel Licht absorbieren.

<div class="mw-heading mw-heading2"><h2 id="Kritik">Kritik</h2></div>

Gavin S. P. Miller hat den Diamond-square Algorithmus kritisiert, da er, im Gegensatz zu dem von ihm vorgestellten <a href="Square-square_Algorithmus" title="Square-square Algorithmus">Square-square Algorithmus</a>, zu auffälligen Artefakten in der generierten Landschaft führt<a href="#cite_note-miller1986definition-2">[2]</a>.

Fraktale Landschaften im Allgemeinen stehen in der Kritik, da sie zwar eine gute Approximation für Bergzüge liefern, die Landschaften jedoch – stellt man sie auf den Kopf – statistisch identisch sind<a href="#cite_note-5">[5]</a>. In der Realität lagern sich jedoch beispielsweise Sedimente in Talsenken ab, wodurch diese abflachen. Unter anderem haben Musgrave, Kolb und Mace unter Berücksichtigung von <a href="Erosion_(Geologie)" title="Erosion (Geologie)">Erosion</a>seffekten eine Weiterentwicklung fraktaler Landschaften entwickelt, die in der Lage ist, Landschaften zu erzeugen, die wesentlich realitätsnäher sind.

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li>Async Drink: <a rel="nofollow" class="external text" href="https://asyncdrink.com/blog/diamond-square-algorithm">Generating landscapes with the Diamond Square algorithm</a></li>

<li>Robert C. Martin, The Clean Code Blog <a rel="nofollow" class="external text" href="https://blog.cleancoder.com/uncle-bob/2017/01/09/DiamondSquare.html">TDD Lesson - Terrain Generation</a></li>

<li><a rel="nofollow" class="external text" href="https://gist.github.com/awilki01/83b65ad852a0ab30192af07cda3d7c0b">Diamond-square Implementierung in C#</a></li>

<li><a rel="nofollow" class="external text" href="https://github.com/A1essandro/Diamond-And-Square">Diamond-square Implementierung in PHP</a></li>

<li>Fractal terrain generator: <a rel="nofollow" class="external text" href="https://spbooth.github.io/xmountains/">Xmountains</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-fournier1982computer-1">↑ <a href="#cite_ref-fournier1982computer_1-0">a</a> <a href="#cite_ref-fournier1982computer_1-1">b</a> A. Fournier,D. Fussell und L. Carpenter: Computer rendering of stochastic models In: Communications of the ACM, Band 25, Nr. 6, 1982, S. 371–384

</li>

<li id="cite_note-miller1986definition-2">↑ <a href="#cite_ref-miller1986definition_2-0">a</a> <a href="#cite_ref-miller1986definition_2-1">b</a> Gavin S. P. Miller: The definition and rendering of terrain maps In: ACM SIGGRAPH Computer Graphics, Band 20, Nr. 4, 1986, S. 39–48

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Robert C. Pendleton: <a rel="nofollow" class="external text" href="https://web.archive.org/web/20060420054134/http://www.gameprogrammer.com/fractal.html#diamond">Generating Random Fractal Terrain</a>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">↑</a> GitHub: <a rel="nofollow" class="external text" href="https://gist.github.com/awilki01/83b65ad852a0ab30192af07cda3d7c0b">Diamond-Square Algorithm for Generating Terrain (C#)</a>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">↑</a> F.K. Musgrave, C.E. Kolb und R.S. Mace: The synthesis and rendering of eroded fractal terrains In: ACM SIGGRAPH Computer Graphics, Band 23, Nr. 3, 1989, S. 41–50

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-06-17" href="https://de.wikipedia.org/wiki/?title=Diamond-square_Algorithmus&oldid=245976557">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>